import pprint as pp
class Solution:
	# @param {string} s
	# @return {string}
	def longestPalindrome(self, s):
	    n=len(s)
	    if n <2:
	        return s
	    Q2 = set()
	    Q3 = set()
	    Length = 1
	    longestP = s[0]
	    for i in xrange(n-2):
	        if s[i] == s[i+1]:
	            Q2.add((i,i+1)) 
	        if s[i] == s[i+2]:
	            Q3.add((i,i+2))
	    if s[n-2] == s[n-1]:
	        Q2.add((n-2,n-1))
	    if Q3:
	        Length = 3
	        longestP = Q3.pop()
	        Q3.add(longestP)
	    if Length<3 and Q2 :
	        Length = 2
	        longestP = Q2.pop()
	        Q2.add(longestP)
	    while Q2 or Q3:
	        if len(Q3)>=len(Q2):
	            curr = Q3
	            offset = 1
	        else:
	            curr = Q2
	            offset = 0
	        start, end = curr.pop()
	        if end - start > 2:
	        	print start,end
	        middle = (start+end)/2

	        # if substring is at start or end, continue
	        if (middle-(Length+offset)/2<0) or (middle+(Length+offset)/2+1-offset >n-1):
	            #print "break"
	            continue

	        longer = True
	        for i in reversed(range((end-start-offset+1)/2+offset,(Length+offset)/2+1)):

	            if s[middle-i] != s[middle+i+1-offset]:
	                longer = False
	                break
	        if not longer:
	            continue

	        while True:
	            i+=1

	            if middle-i<0 or middle+i+1-offset>=n-1:                    
	                break
	            if s[middle-i] != s[middle+i+1-offset]:                    
	                break

	        i-=1
	        Length = 2*(i+1)-offset
	        longestP = (middle-i, middle+i+1-offset)
	        curr.add(longestP)

	    start, end = longestP
	    return s[start:end+1]

'''
1. This algorithm firstly traverses the string, which is O(n), adding all 2-item & 3-item 
   palindrome sub-strings to the sets.
2. There are O(n) number of small sub-strings and they will be examined at least one time.
3. In the best cases the longest candidate is examined firstly. Finding `longestP` cost O(n/2)
   Then use O(n) time to exclude other sub-strings. So the examine process cost O(1.5*n)
4. In the worst cases, `Length` grows steadily. There will be O(sqrt(2*n)) new sub-strings to
   be added to the sets. So the examine process cost O(2 * sqrt(2*n) + n)
5. Thus, it's O(n)
'''

if __name__ == '__main__':
	print Solution().longestPalindrome('ffffffffffffffffffffffffffffffffffffffffffff')

